#include<bits/stdc++.h>
using namespace std;

int a[] = {0, 0, 1, 1, 2, 1};

int main()
{
	long long n;
	while(cin>>n)
	{
		if(n < 6)
			cout<<a[n]<<endl;
		else if(n%2 == 0)
			cout<<"2"<<endl;
		else
		{
			int flag = 0;
			for(int i = 2;i <= sqrt(n);i++)
				if(n%i == 0)
					flag = 1;
			if(!flag)
			{
				cout<<1<<endl;
				continue;
			}
			
			flag = 0;
			n -= 2;
			for(int i = 2;i <= sqrt(n);i++)
				if(n%i == 0)
					flag = 1;
			if(flag)
				cout<<"3"<<endl;
			else
				cout<<"2"<<endl;
		}
	}
	return 0;
}

